import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-06-08
 * Time: 14:53
 */

// 牛客 ： [编程题]不用加减乘除做加法

class Solution37 {
    /*
    异或操作：把2个数相加过程中对应位的那2个位只有一个位为1的情况，都给找到了（相同为0，不同为1）
    与操作：把2个数相加过程中相对应的那2个位都为1，就是（有2个1）的情况都给找到了（2个都为1则为1，否则为0）
    然后左移一位的操作：就是把那些 通过与操作 所找到的那些2个位都是1的位置进行了相当于向前进位的操作，整体左移了一位，（就好像进位了）
    */
    public int Add(int num1,int num2) {
        // 位运算
        if(num1==0 || num2==0){
            return (num1==0)?num2:num1;
        }

        int ret1=num1^num2;
        int ret2=num1&num2;
        int ret3=ret2<<1;

        return Add(ret1,ret3);
    }
}










// 1. 两数之和

class Solution36 {
    public int[] twoSum(int[] nums, int target) {
        // 新思路
        //hash表的查找效率是O(1)的

        //遍历数组，得到用target-数组nums[i]的值，去hash表里面寻找，
        //找到了就返回找到的这2个数的下标值，
        //要是没找到，就把数组中的  这个数以及他对应的下标值   放到hash中去
        HashMap<Integer,Integer> map=new HashMap<>();
        //这个map的<key,value>值的对应关系是：key对应数组nums[i]值，value对应数组的下标值i
        int len=nums.length;

        int[] arr=new int[2];
        for(int i=0;i<len;i++){
            int ret=target-nums[i];
            arr[0]=i;
            //判断ret是否存在于map中
            if(map.containsKey(ret)){
                //存在
                arr[1]=map.get(ret);
                break;
            }else{
                //不存在
                //把这<nums[i],i>的键值对放到map中
                map.put(nums[i],i);
            }
        }

        return arr;
    }
}











// 91. 解码方法 的优化版本（优化地方：初始化）

class Solution35 {
    public int numDecodings(String s) {
        //动态规划，并且进行与我之前写法上面的优化版本
        //一位一位遍历这个s字符串，得到它每一位的字符内容，然后大体分为2种情况进行考虑：
        // 1，此位单独进行解码操作
        // 2.此位于它的前一位联合解码
        //把这2种情况下得到的解码数值进行相加操作
        //设置dp表：dp[i]的含义：s字符串中【0，i-1】的位置，有多少种解码方式
        //有一些优化的点在于dp表的数组范围大小多了1位，让这个第一位变成了一个 虚拟节点的作用，这样子做，我们就只需要初始化原来的【0，0】的解码方法数，对于【0，1】的解码方法数就可以放到后面求解，而不需要我们一开始进行初始化了
        int len=s.length();
        int[] dp=new int[len+1];
        dp[0]=1;
        char ch=s.charAt(0);
        if(ch>='1' && ch<='9'){
            //对dp[1]的位置进行初始化，肯定是只能独自解码，所以如果ch这个字符的范围是在[1,9]那就说明【0，0】这个范围是有一种解码方法的，要不然就是有0种解码方法
            dp[1]=1;
        }

        //字符串s中字符的位置下标 a ，与dp表中的下标 b 的对应关系为：a+1=b
        for(int i=1;i<len;i++){
            ch=s.charAt(i);
            int m=0;//用m来存放单独解码的方案数
            int n=0;//用n来存放联合解码的方案数
            //i位置单独解码
            if(ch>='1' && ch<='9'){
                m=dp[i];
            }
            //i位置和它的前一个位置联合解码
            char ch1=s.charAt(i-1);
            int num=(ch1-'0')*10 + ch-'0';
            if(num>=10 && num<=26){
                n=dp[i-1];
            }

            dp[i+1]=m+n;
            //有一个位置区间解码不了，那整体来说就解码不了
            if(dp[i+1]==0){
                return 0;
            }
        }


        return dp[len];
        //我们要的是 要把这个s字符串整体解码成功的方案数，所以当然要返回dp数组的最后一位的值
    }
}













// 91. 解码方法

class Solution34 {
    public int numDecodings(String s) {
        // 动态规划的思想
        // 有一些特殊情况：如果遇到类似于60这样的，那就说明这个字符串解码失败了
        // 有一些特殊情况：如果遇到类似于06这样的，那就说明这个字符串解码也失败了

        //从前往后
        //dp数组中：dp[i]表示的是 从数组初始位置到i位置有多少种解码方案
        //dp[i]表示的是 以i位置为结尾有多少种解码方案。
        int len=s.length();
        int[] dp=new int[len];

        //初始化
        // 我们这个dp数组 ： dp[i]这个位置的值和谁有关？
        // dp[i] 的值和 dp[i-1] 和 dp[i-2] 有关，也和字符串在i下标的对应的数字字符和i-1下标对应的数字字符有关

        // 所以我们应该把dp[0]和dp[1]进行初始化
        // dp[0]的值也有2种情况：也就是只有一个字符的情况
        // 1.它的值为0那就直接返回0
        // 2.它的值不为0，那就赋值为1
        char ch=s.charAt(0);
        if(ch=='0'){
            return 0;
        }else{
            dp[0]=1;
        }

        // 当我们要去初始化dp[1]的时候，也需要看一下s字符串的长度，如果这个字符串的长度是1那么就直接返回，要不然就初始化dp[1]然后继续往下走
        if(len==1){
            return dp[0];
        }else{
            //初始化dp[1]的值：也就是只有2个字符的情况
            // 1.如果第一位为0，那就直接返回0：【 06 】无法解码的情况
            // 2.第一位不为0： 【12】就有2种解码方式 [1和2] 与 [12] ； 【66】 就有一种解码方式。
            if(s.charAt(0)=='0'){
                return 0;
            }else{
                int ch1=(int)s.charAt(0)-48;
                int ch2=(int)s.charAt(1)-48;
                int ret=ch1*10+ch2;
                if(ret>10 && ret<=26 && ret!=20){
                    dp[1]=2;
                }else if(ret==10 || ret==20 || ret>26 && ch2!=0){
                    //对于ret的值，如果是10或者20还是有对应的字符的 【ret==10 || ret==20】
                    //但是如果ret的值已经超过了26，然后再遇到类似于 30，40，50这样的情况，就是无法表示的了，就应该拿出来讨论一下 【ret>26 && ch2!=0】
                    dp[1]=1;
                }
            }
        }

        // 开始遍历字符串，然后寻找dp数组的元素值
        int i=2;
        while(i<len){
            ch=s.charAt(i);

            int a=0; // 用来记录字符单独解码的方案数
            int b=0; // 用来记录2个字符联合编码的方案数
            //对i在字符串中对应的数字字符进行单独解码
            // 1.这个字符不为0，那么就是a=dp[i-1]
            // 2.这个字符为0，那么a=0
            if(ch!='0'){
                a=dp[i-1];
            }else{
                a=0;
            }
            //对i在字符串中对应的数字字符不进行单独解码，而是和i-1对应的数字字符进行联合解码
            // 1.联合起来的字符的范围在：【10，26】，符合条件，那么 b=dp[i-2]
            // 2.联合起来的字符的范围不在：【10，26】，那么b=0
            int ch1=(int)s.charAt(i-1)-48;
            int ch2=(int)s.charAt(i)-48;
            int ret=ch1*10+ch2;

            if(ret>=10 && ret<=26){
                b=dp[i-2];
            }else{
                b=0;
            }


            // dp[i]的值 是a与b的和
            //dp[i]表示的是 以i位置为结尾有多少种解码方案。
            dp[i]=a+b;




            i++;
        }

        // 返回值
        // dp[i]表示的是 以i位置为结尾有多少种解码方案。
        return dp[len-1];
    }
}











// 746. 使用最小花费爬楼梯

class Solution33 {
    //要注意对楼顶位置的理解
    public int minCostClimbingStairs(int[] cost) {
        // 看示例一的解释：我们发现楼顶的位置并不在数组的最后一个元素的位置，而是在数组最后一个的位置的 后面呢

        int len=cost.length;
        // 创建一个dp数组，dp[i]代表从起始位置到i位置的最低花费。
        int[] dp=new int[len];

        // dp[i]数组中这个位置的值和它的dp[i-1]和dp[i-2]位置  中的最小值有关
        // 所以我们可以先初始化一下dp数组的前2个位置，防止越界
        //因为题目要求数组的长度是大于等于2的，所以就直接初始化dp数组的前2个位置就可以了
        dp[0]=0;
        dp[1]=0;

        int i=2;
        while(i<len){
            // dp[i]中存的值是min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])中的较小值
            int a=dp[i-1]+cost[i-1];
            int b=dp[i-2]+cost[i-2];

            dp[i]=a>b?b:a;

            i++;
        }


        // 最后要返回的结果是 min(dp[len-2]+cost[len-2],dp[len-1]+cost[len-1]) 中的较小值
        int c=dp[len-1]+cost[len-1];
        int d=dp[len-2]+cost[len-2];

        int nums=c>d?d:c;
        return nums;
    }
}
















// 面试题 08.01. 三步问题

class Solution32 {
    // 动态规划

    public int waysToStep(int n) {
        //上一阶台阶只有： 0->1   这一种
        //上2阶台阶有：0->2  0->1->2 这2种
        //上3阶台阶有： 0->3    0->1->2->3   0->1->3   0->2->3   这4种
        long[] arr={1,2,4};//初始化
        if(n==1){
            return (int)arr[0];
        }else if(n==2){
            return (int)arr[1];
        }else if(n==3){
            return (int)arr[2];
        }
        //状态转移方程：  dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

        int p=4;//表示现在已经到第几个台阶了
        while(p<=n){
            long ret=arr[0]+arr[1]+arr[2];
            arr[0]=arr[1];
            arr[1]=arr[2];
            arr[2]=ret;
            p++;

            //为了防止溢出，用long类型来接收中间结果
            //为了防止溢出，%1000000007来把数变小了
            arr[0] %= 1000000007;
            arr[1] %= 1000000007;
            arr[2] %= 1000000007;

        }

        // 题目要求：结果可能很大，你需要对结果模1000000007。
        return (int)(arr[2]%1000000007);
    }
}














// 860. 柠檬水找零

class Solution31 {
    public boolean lemonadeChange(int[] bills) {

        int[] arr=new int[2];//数组的0下标的位置负责记录：我有几个5元
        //数组的1下标的位置负责记录：我有几个10元

        int len=bills.length;//bills数组的长度

        for(int i=0;i<len;i++){
            int ret=bills[i];
            if(ret==5){
                //收到一张5元的
                arr[0]++;
            }else if(ret==10){
                //收到一张10元的
                if(arr[0]==0){
                    //我没有5元的了，无法找零了
                    return false;
                }else if(arr[0]!=0){
                    //给顾客一张5元的，我收到了一张10元的
                    arr[0]--;
                    arr[1]++;
                }
            }else if(ret==20){
                //收到一张20元的
                if(arr[1]!=0 && arr[0]!=0){
                    arr[1]--;
                    arr[0]--;
                    //找给顾客一个十元的一个五元的
                }else if(arr[1]==0 && arr[0]>=3){
                    arr[0]-=3;
                    //找给顾客三张五元的
                }else{
                    //找不到，找不开零了
                    return false;
                }

            }

        }


        return true;
    }
}











// 2558. 从数量最多的堆取走礼物

class Solution30 {
    public long pickGifts(int[] gifts, int k) {
        // 向下取整 :往小了取
        // 1.1 就取为 1
        // 排序进行操作，要不然得一遍一遍的遍历了,
        //排序的话，时间复杂度肯定是超过O(N)了
        //毕竟每次找到一个最大值以后，还要再排序一次
        //所以还是遍历找最大比较好，这样子的  每次   找最大值的  时间复杂度   就是：O(N)了

        // 根号1是1,当一个数组的所有元素都是1的时候，就直接返回数组的长度就可以了， 此时就如示例2所说了
        int one=0;//设立一个one的位，来看每次遍历数组的时候 ，是否这个数组的元素都为1
        int big=0;//设立big去找每次遍历数组的最大值
        int p=0;//设立p是为了去找每次遍历数组的最大值的下标值
        int len=gifts.length; //数组的长度
        int m=1;// 记录走到第几秒了

        while(m<=k){
            one=0;
            big=0;
            p=0;
            for(int i=0;i<len;i++){
                if(gifts[i]==1){
                    one++;
                    //数组元素为1 就++
                }
                if(gifts[i]>big){
                    //找最大值的过程
                    big=gifts[i];
                    p=i;
                }
            }

            if(one==len){
                //当一个数组的所有元素都是1的时候，就直接返回数组的长度就可以了， 此时就如示例2所说了
                return len;
            }

            //找到这次遍历的最大值了
            //把最大值位置的值改成它的 平方根之后的值
            gifts[p]=(int)Math.pow(big,0.5);


            m++;
        }



        // 返回值记得用long类型
        long num=0;// 放置最终将要返回的结果
        for(int i=0;i<len;i++){
            num+=gifts[i];
        }

        return num;
    }
}














//89. 格雷编码


class Solution29 {
    //思路：找规律。有一种对称的关系在里面
    //找规律法:
//n位格雷码可以由n-1位格雷码ret所推出
//找的规律就是: 对称式的再push加 对称位置的原数 + pow(2,n-1) 即可
//如[0,1,3,2](n==2),然后[0,1,3,2,6,7,5,4](n==3)，n==3是从n==2对称相加来的，如下：
//[0,1,3,2    6,7,5,4] >>>:  2+pow(2,2)->6 ,  3+pow(2,2)->7 ,  1+pow(2,2)->5 ,  0+pow(2,2)->4




    public  List<Integer> list=new ArrayList<>();


    public  List<Integer> grayCode(int n) {
        int len=(int)Math.pow(2,n);

        if(list.size()==0){
            list.add(0); //可以先把list的第一位填上去，一定为0
        }


        if(list.size()>=len){
            return list;
        }


        int ret=1;
        while(ret<=n){


            int m=(int)Math.pow(2,ret-1);

            //遍历list，找到接下来可以放到list中的2^(ret-1)个数
            int size=list.size();
            for(int i=size-1;i>=0;i--){
                int num=list.get(i);
                list.add(num+m);
            }

            ret++;
        }

        //也就是说[0, 2n - 1]这个范围内的所有数字都会被放到list中


        // 然后我们去找下一个数
        // 有一种对应关系

        //按照一种对称的关系来解决问题
        //一会说一下这个对称关系
        //好像也得递归求解

        return list;

    }
}















//17.电话号码的字母组成

class Solution28 {


    public  List<String> letterCombinations(String digits) {
        //找到字符串数组中的每一个数字字符所对应的字母，然后进行排列组合，回溯算法
        //先把各个数字对应的字符串对应的放到二维数组里面
        String[][] str={{"2","abc"},{"3","def"},{"4","ghi"},{"5","jkl"},{"6","mno"},{"7","pqrs"},{"8","tuv"},{"9","wxyz"}};

        int len=digits.length(); // digits 字符串 的长度

        String[] strings=new String[len]; //存放 digits 字符串 各个字符所对应的 字符串组合放到这个字符串数组中
        int j=0; // 用来记录strings数组走到哪里了

        // 开始遍历digits这个字符串，来找到它每个数字字符所对应的字母字符串 放到strings数组中
        for(int i=0;i<len;i++){
            char ret=digits.charAt(i);
            int rett=(int)ret-48; // 使用数字字符和数字的关系，把char强转成 int 来使用

            int rettt=rett-2; //得到下标

            strings[j++]=str[rettt][1]; // 找到了，放到strings数组中
        }


        //得到我们要的字符串数组strings了
        //要和其他的字符串中的字符进行组合,不和自己本字符串的字符进行组合
        // 输入：digits = "23"
        // 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

        if(digits.length()==0){
            //如果digits字符串为空串，就直接返回
            return list;
        }

        // 调用子方法，进行回溯递归
        func(strings,0);

        return list;

    }

    List<String> list=new ArrayList<>();  //用来存放最终结果
    List<Character> array=new ArrayList<>();// 用来存放中间结果

    public  void func(String[] strings,int m){

        //m 是来标记strings这个数组走到哪个下标了
        if(m>strings.length){
            return;
        }

        //递归终止条件：当记录中间路径的字符串的长度达到strings数组的长度的时候就可以添加到最终结果中，并返回了
        if(array.size()==strings.length){
            //记得把array这个字符数组变成一个字符串然后放到list中
            String tmp="";
            for(int j=0;j<array.size();j++){
                tmp+=array.get(j);
            }
            list.add(tmp);
            return ;
        }

        //每次往下递归一个串
        String str1=strings[m];
        int len1=str1.length();


        for(int i=0;i<len1;i++){
            //回溯的过程
            array.add(str1.charAt(i));

            //递归回溯
            func(strings,m+1);

            //恢复现场
            if(array.size()>0){
                array.remove(array.size()-1);
            }

        }
    }




}












// 15. 三数之和

class Solution27 {



    public   List<List<Integer>> threeSum(int[] nums) {
        // 下标值不同的三个下标 对应的数组中的三个值加起来的值为0
        //  nums[i] + nums[j] + nums[k] == 0

        // 这个数组的长度是一定大于等于3的，而且如果这个数组中没有我们想要的,,,就需要直接返回一个空的list就行了
        int len=nums.length;

        // 对数组进行排序
        Arrays.sort(nums);

        List<List<Integer>> list=new ArrayList<>();//存放threeSum方法的最终返回值

        // 对数组进行排序，然后设立类似于三个指针，一个为i,一个为left==i+1，一个为right=len-1，然后让i从0到len-1开始for循环
        // 让left和right逐步接近，在这个过程中 要注意left<right 以及下标left,right和i 对应的值相加的和num是否为0,为零的话就可以放到list中了，然后让left++
        // 不为0的时候，如果大于零，就让right--,如果小于0，就让left++

        // 让i从0到len-1开始for循环
        for(int i=0;i<len;i++){

            //这一步的if是为了避免相等值被重复使用到
            // 例如：nums = [-1,0,1,2,-1,-4]
            /// 排好序之后是：【-4，-1，-1，0，1，2】
            //为了不让i下标对应的值出现重复的现象，所以要在此处加上这个if的判断
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }

            // 设立类似于三个指针，一个为i,一个为left==i+1，一个为right=len-1，
            int left=i+1;
            int right=len-1;

            // 让left和right逐步接近，在这个过程中 要注意left<right
            while(left<right){
                int num=nums[i]+nums[left]+nums[right];
                if(num==0){
                    List<Integer> arr=new ArrayList<>();
                    arr.add(nums[i]);
                    arr.add(nums[left]);
                    arr.add(nums[right]);
                    // num 为零的话就可以放到list中了，然后让left++
                    list.add(new ArrayList<>(arr));

                    int leftVal = nums[left];
                    int rightVal = nums[right];
                    // 为了跳过和left下标值相等的下标，对应数组中的值相等的下标是没有使用价值的
                    while(left < right && nums[left] == leftVal)
                        left++;

                }else if(num>0){
                    // 如果大于零，就让right--
                    right--;
                }else if(num<0){
                    // 如果小于0，就让left++
                    left++;
                }
            }
        }

        return list;
    }






}













// 7. 整数反转

class Solution26 {




    // 题目要求的范围：[−231,  231 − 1] 正好是int类型的范围
    public static int reverse(int x) {
        // 如果这个数有10位，就是要翻转过来倒过来
        // 得到它的每一位，存在ArrayList中，然后倒着取出，然后比较大小
        //ArrayList的大小可以作为10的几次幂来使用
        // 应该会使用到 10的几次幂的Math方法
        // 可以计算一下2的31次幂
        // 超过整数范围就返回 0


        //先判断一下x值的正负，然后把这个符号的信息给记录下来
        boolean bool=true;
        if(x>0){
            bool=true;//x是一个正数
        }else{
            bool=false;//x是一个负数
        }




        ArrayList<Integer> list=new ArrayList<>();

        //当x不为0的时候就一直，while循环下去
        //如何得到一个数的每一位的数字呢???
        //x%10得到的余数就是它的末位
        //然后x除以10得到接下来的x值
        //直到x为0为止
        while(x!=0){

            // 让这个list中存的数都是正数：
            list.add(Math.abs(x%10));

            x=x/10;
        }



        //走到这里 x的值已经是0了，所以说x的每一位我们也都已经获得了，可以开始求出把他倒过来的数值了，最好用long类型来接收，因为可能已经超过了int的范围
        int size=list.size();
        int n=size; // 使用n来表示幂指数

        //所以说倒过来以后最大的幂指数是 size-1 也就是 n-1 ，然后依次减一
        long num=0;//用来存放最终要返回的结果，也就是倒过来加起来的值存在num中
        for(int i=0;i<size;i++){
            int ret=list.get(i);
            num+=ret*Math.pow(10,n-1);
            n--;
        }



        int a=Integer.MAX_VALUE;//int类型的最大值
        int b=Integer.MIN_VALUE;//int类型的最小值


        if(bool==false){
            //说明num应该是一个负数，我们也需要把它变成一个负数
            num*=(-1);
        }


        // 然后比较是否超过了可表示的范围，没有超过就返回，超过了就返回 0
        if(num>=b && num<=a){
            return (int)num;
        }

        return 0;

    }




}







// 401. 二进制手表

class Solution25 {

    public  List<String> readBinaryWatch(int turnedOn) {
        int[] arr1={8,4,2,1}; // 小时的那4个灯
        int[] arr2={1,2,4,8,16,32}; // 分钟的那6个灯
        List<String> list=new ArrayList<>(); // 用来存放最终被返回的结果

        // 把turnedOn个灯分给小时灯和分钟灯，要注意范围，毕竟小时灯只有4个，分钟灯只有6个
        for(int i=0;i<=4;i++){
            int j=turnedOn-i;
            // i+j==turnedOn
            // 当分钟灯要求的个数超过了6个的时候，说明这个组合不合适，就继续寻找下一组合
            if(j>6){
                continue;
            }



            Set<Integer> array11=new HashSet<>(); //存放最终结果的数组
            List<Integer> array1=new ArrayList<>(); // 存放中间结果的数组（存放的是一条路径中的数据组成的数组）
            boolean[] check1=new boolean[4]; // 用来剪枝,false代表这个元素在这一条路径中还没有被用到,true则代表被用过了

            func1(arr1,i,array11,array1,check1);// 从小时的那4个灯中拿出 i 灯来 并返回小时的结果




            Set<Integer> array22=new HashSet<>(); //存放最终结果的数组
            List<Integer> array2=new ArrayList<>(); // 存放中间结果的数组（存放的是一条路径中的数据组成的数组）
            boolean[] check2=new boolean[6]; // 用来剪枝,false代表这个元素在这一条路径中还没有被用到,true则代表被用过了

            func2(arr2,j,array22,array2,check2);// 从分钟的那6个灯中拿出 j 灯来 并返回分钟的结果






            Set<Integer> set11=array11; // 得到小时有i个灯亮起来的所有可能的结果
            Set<Integer> set22=array22; // 得到分钟有j个灯亮起来的所有可能的结果


            // 遍历set1和set2 然后排列组合，把每次组合的结果都放到list中，
            // 要小心set2这个分钟小于10的时候，需要在前面填一个0的情况

            // 小时除了0不会以0开头，分钟则必须由两位组成
            //小时的范围是：（0-11）
            //分钟的范围数：（0-59）
            for(Integer s1 : set11){
                for(Integer s2 : set22){

                    ///小时的范围是：（0-11）
                    if(s1<=11){
                        if(s2<10){
                            // 分钟则必须由两位组成(所以当分钟的值小于10，也就是为一位的时候，我们需要给他补上一位0)
                            list.add(s1+":0"+s2);
                        }else if(s2>=10 && s2<=59){
                            //要注意分钟的范围数：（0-59）
                            list.add(s1+":"+s2);
                        }
                    }else if(s1>11){
                        //小时的范围是：（0-11）
                        //超过小时的范围了就不是正确答案了，就break掉这层的for循环
                        break;
                    }

                }
            }
        }

        return list;
    }



    // 从小时的那4个灯中拿出 n 灯来返回小时的结果
    public void func1(int[] arr1,int n,Set<Integer> array11,List<Integer> array1,boolean[] check1){
        if(array1.size()==n){
            //递归出口
            int ret=0;
            //把这条路径上的小时的值相加，把ret这个结果放到array11中
            for(int i=0;i<n;i++){
                ret+=array1.get(i);
            }

            array11.add(ret);
            return ;
        }


        for(int i=0;i<arr1.length;i++){
            //遍历arr1数组，找到路径中没有使用到的数组元素，找到一个就放一个，然后调用func1进行递归
            if(check1[i]==false){
                array1.add(arr1[i]);
                check1[i]=true;

                func1(arr1,n,array11,array1,check1);

                //回溯
                if(array1.size()>0){
                    array1.remove(array1.size()-1);
                    check1[i]=false;
                }
            }
        }
    }



    // 从分钟的那6个灯中拿出 n 灯来返回分钟的结果
    public  void func2(int[] arr2,int n,Set<Integer> array22,List<Integer> array2,boolean[] check2){

        if(array2.size()==n){
            //递归出口
            int ret=0;
            //把这条路径上的小时的值相加，把ret这个结果放到array22中
            for(int i=0;i<n;i++){
                ret+=array2.get(i);
            }

            array22.add(ret);
            return ;
        }


        for(int i=0;i<arr2.length;i++){
            //遍历arr2数组，找到路径中没有使用到的数组元素，找到一个就放一个，然后调用func2进行递归
            if(check2[i]==false){
                array2.add(arr2[i]);
                check2[i]=true;

                func1(arr2,n,array22,array2,check2);

                //回溯
                if(array2.size()>0){
                    array2.remove(array2.size()-1);
                    check2[i]=false;
                }
            }
        }

    }
}













// 48. 旋转图像

class Solution24 {
    public void rotate(int[][] matrix) {
        // n*n的一个矩阵
        // 顺时针旋转90度
        // 在原有数组中进行修改

        //基本思路把这个数组的一圈的元素以顺时针的方向从左上角开始取出
        //然后再从右上角开始顺时针的方向，把取出的这一圈数字再放回到数组中（进行覆盖）

        //设计一个子函数来完成递归的过程，一圈一圈的取出，然后以另一种顺序一圈一圈的放回去
        func(matrix,matrix.length,0,0);

    }

    // 子函数，完成递归的过程
    //设计一个子函数来完成递归的过程，一圈一圈的取出，然后以另一种顺序一圈一圈的放回去
    public void func(int[][] array,int size,int x,int y){
        // x是行,y列

        if(size<=1){
            //size*size的子数组，当size的大小小于等于1的时候，就递归结束了.
            return;
        }

        //size为4举例：那一圈就有 12 个数字:2*size+2*(size-2)
        //size为2举例：那一圈就有 4 个数字
        int[] arr=new int[2*size+2*(size-2)];//用来存放大小为size的一圈的所以元素
        int ret=0;//用来表示arr数组的下标


        int i=x;//用来表示行坐标
        int j=y;//用来表示列坐标

        //开始从左上角开始遍历一圈
        //向右走，行坐标不变
        i=x;
        for(j=y;j<=y+size-1;j++){
            arr[ret]=array[i][j];
            ret++;
        }
        //向下走，列坐标不变
        j=y+size-1;
        for(i=x+1;i<=x+size-1;i++){
            arr[ret]=array[i][j];
            ret++;
        }
        //向左走，行坐标不变
        i=x+size-1;
        for(j=y+size-2;j>=y;j--){
            arr[ret]=array[i][j];
            ret++;
        }
        //向上走，列坐标不变
        j=y;
        for(i=x+size-2;i>=x+1;i--){
            arr[ret]=array[i][j];
            ret++;
        }



        ret=0;
        //可以开始以另一种顺序来把这一圈的数字再放回去了
        //从右上角开始放
        //向下走，列坐标不变
        j=y+size-1;
        for(i=x;i<=x+size-1;i++){
            array[i][j]=arr[ret];
            ret++;
        }
        //向左走，行坐标不变
        i=x+size-1;
        for(j=y+size-2;j>=y;j--){
            array[i][j]=arr[ret];
            ret++;
        }
        //向上走，列坐标不变
        j=y;
        for(i=x+size-2;i>=x;i--){
            array[i][j]=arr[ret];
            ret++;
        }
        //向右走，行坐标不变
        i=x;
        for(j=y+1;j<=y+size-2;j++){
            array[i][j]=arr[ret];
            ret++;
        }


        //继续递归下一圈（size==size-2）
        func(array,size-2,x+1,y+1);
    }
}









// 36. 有效的数独

class Solution23 {
    public boolean isValidSudoku(char[][] board) {
        // 按照题目来看，这一定是1个9*9的二维数组了
        // 我们所需要做的就是先整体来看这个二维数组的每一行，每一列中是否有重复的数字字符
        // 然后，看分出来的3*3的子数组中是否有重复的数字字符。


        int[] arr=new int[9];//用来存放1~9这9个字符在一行中出现的次数
        for(int i=0;i<9;i++){
            arr=new int[9];//用来存放1~9这9个字符在一行中出现的次数
            //一行一行遍历
            for(int j=0;j<9;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }

        arr=new int[9];//用来存放1~9这9个字符在一列中出现的次数
        for(int i=0;i<9;i++){
            arr=new int[9];//用来存放1~9这9个字符在一列中出现的次数
            //一列一列遍历
            for(int j=0;j<9;j++){
                //得到的数字字符转换成int，然后减一
                if(board[j][i]!='.'){
                    int ret=((int)board[j][i])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }


        //遍历那九个3*3的子数组
        // 范围分别为：共会有9个范围

        // [0,2] [0,2]
        arr=new int[9];//用来存放1~9这9个字符在一个3*3的子数组中出现的次数
        for(int i=0;i<=2;i++){

            //遍历
            for(int j=0;j<=2;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }

        // [0,2] [3,5]
        arr=new int[9];//用来存放1~9这9个字符在一个3*3的子数组中出现的次数
        for(int i=0;i<=2;i++){

            //遍历
            for(int j=3;j<=5;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }

        // [0,2] [6,8]
        arr=new int[9];//用来存放1~9这9个字符在一个3*3的子数组中出现的次数
        for(int i=0;i<=2;i++){

            //遍历
            for(int j=6;j<=8;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }

        // [3,5] [0,2]
        arr=new int[9];//用来存放1~9这9个字符在一个3*3的子数组中出现的次数
        for(int i=3;i<=5;i++){

            //遍历
            for(int j=0;j<=2;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }

        // [3,5] [3,5]
        arr=new int[9];//用来存放1~9这9个字符在一个3*3的子数组中出现的次数
        for(int i=3;i<=5;i++){

            //遍历
            for(int j=3;j<=5;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }

        // [3,5] [6,8]
        arr=new int[9];//用来存放1~9这9个字符在一个3*3的子数组中出现的次数
        for(int i=3;i<=5;i++){

            //遍历
            for(int j=6;j<=8;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }

        // [6,8] [0,2]
        arr=new int[9];//用来存放1~9这9个字符在一个3*3的子数组中出现的次数
        for(int i=6;i<=8;i++){

            //遍历
            for(int j=0;j<=2;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }

        // [6,8] [3,5]
        arr=new int[9];//用来存放1~9这9个字符在一个3*3的子数组中出现的次数
        for(int i=6;i<=8;i++){

            //遍历
            for(int j=3;j<=5;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    //ret是数字字符所对应的在arr数组中的下标
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }

        // [6,8] [6,8]
        arr=new int[9];//用来存放1~9这9个字符在一个3*3的子数组中出现的次数
        for(int i=6;i<=8;i++){

            //遍历
            for(int j=6;j<=8;j++){
                //得到的数字字符转换成int，然后减一
                if(board[i][j]!='.'){
                    int ret=((int)board[i][j])-49; // 所以数值型1和字符型1的ascii码是一样的，都是49。
                    arr[ret]++;
                    if(arr[ret]>1){
                        return false;
                    }
                }
            }
        }



        return true;

    }
}












// 125. 验证回文串

class Solution22 {
    //验证回文串

    public boolean isPalindrome(String s) {
        //如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
        //
        //字母和数字都属于字母数字字符。

        //我们拿到这个字符串之后要把他的非数字和非小写字母的都跳过不算
        //不过在这之前，我们需要把大写字符变成小写字符才可以


        //首先将字符都转换成小写的
        String str=s.toLowerCase();

        int len=str.length();
        //字符串的长度为0，直接返回true就可以了
        if(len==0){
            return true;
        }


        // 走到这里就代表 字符串的长度是大于0 的
        int i=0;
        int j=len-1;
        //让i从头开始遍历，j从尾开始遍历，直到i和j相遇为止

        while(i<=j){
            char ch1=str.charAt(i);
            char ch2=str.charAt(j);
            if(ch1>='a' && ch1<='z'  ||    ch1>='0' && ch1<='9'){
                //ch1是符合规格的字符了
                if( ch2>='a' && ch2<='z'  ||    ch2>='0' && ch2<='9'){
                    //ch2是符合规格的字符了
                    //可以进行比较了
                    if(ch1==ch2){
                        i++;
                        j--;
                        continue;
                    }else{
                        //i和j对应的字符不相等，所以不是回文串，返回false
                        return false;
                    }
                }else{
                    //ch2不是符合规格的字符了
                    j--;
                }
            }else{
                //ch1不是符合规格的字符了
                i++;
            }
        }

        return true;
    }

}









// 412. Fizz Buzz

class Solution21 {
    // 412. Fizz Buzz

    /*
    给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：

    answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
    answer[i] == "Fizz" 如果 i 是 3 的倍数。
    answer[i] == "Buzz" 如果 i 是 5 的倍数。
    answer[i] == i （以字符串形式）如果上述条件全不满足。
     */
    public List<String> fizzBuzz(int n) {

        List<String> list=new LinkedList<>(); //存储结果并最终返回

        //遍历从1到n的所有数字
        for(int i=1;i<=n;i++){
            if(i%3==0 && i%5==0){
                // answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
                list.add("FizzBuzz");
            }else if(i%3==0){
                // answer[i] == "Fizz" 如果 i 是 3 的倍数。
                list.add("Fizz");
            }else if(i%5==0){
                //  answer[i] == "Buzz" 如果 i 是 5 的倍数。
                list.add("Buzz");
            }else{
                //  answer[i] == i （以字符串形式）如果上述条件全不满足。
                list.add(""+i);
            }
        }


        return list;
    }
}





// 24. 两两交换链表中的节点

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution20 {
    public ListNode swapPairs(ListNode head) {
        // 此题为单向链表
        // 节点的个数 会有奇数和偶数的一点区别
        //遍历链表交换相邻2个节点的位置。

        //链表为空
        if(head==null){
            return null;
        }

        // 链表只有一个节点
        if(head.next==null){
            return head;
        }
        //链表只有2个节点
        if(head.next.next==null){
            //交换head和head.next的位置然后返回新的头节点
            ListNode node=head.next;
            head.next=null;
            node.next=head;

            return node;
        }


        //链表的节点个数大于等于3个

        //2个节点为一对，cur表示在原链表中位置靠前的节点
        ListNode cur=head;// cur表示在原链表中  这一对节点中  位置靠前的节点
        ListNode next=head.next;// next表示在原链表中  这一对节点中  位置稍靠后的节点
        ListNode newHead=null;//新链表的头节点
        ListNode newcur=null;//新链表的尾节点

        while(next!=null){
            //每次走2步（走过2个节点）
            // 每次把next先放到新链表中，然后再把cur放到新链表中，最后返回新链表的头节点即可

            ListNode ret=next.next;//next节点的下一个节点

            if(newHead==null){
                //新的头节点为空的情况
                newHead=next;
                newcur=next;
            }else{
                //新的头节点不为空的情况
                //记得更新newcur的指向
                newcur.next=next;
                newcur=next;
            }

            //记得更新newcur的指向
            newcur.next=cur;
            newcur=cur;

            // 记得改变cur的next所指向的节点，防止出现环的情况，
            //让cur的next指向接下来要遍历到的节点ret（走2步之后要遍历到的节点）
            cur.next=ret;
            //然后记得更新cur的指向
            cur=ret;


            //然后更新next的指向
            //当cur已经为空的时候，就把next也置为null，这样就跳出了while循环了
            if(cur!=null){
                next=cur.next;
            }else{
                next=null;
            }

        }

        // 原链表有奇数个节点的情况，当出了while循环以后，应该还剩下一个节点，此时这个节点存在cur中，需要把这个节点也放到新链表的尾部去
        if(cur!=null){
            newcur.next=cur;
            newcur=cur;
        }


        // 记得把新链表的尾节点的next置空
        newcur.next=null;


        //返回新链表的头节点
        return newHead;
    }
}











// LCR 186. 文物朝代判断

class Solution19 {
    public boolean checkDynasty(int[] places) {

        // 并且题目已经保证了数组的大小以及数的范围
        // places.length = 5
        // 0 <= places[i] <= 13
        // 所以直接遍历就行,不用判断是否有效
        // 如遇未知朝代(编号为0的情况)可算作连续情况
        int len=places.length;
        boolean bool=true;

//但是如果非0的值在places数组中出现的次数超过了1次，就属于非连续的了，就返回false

        //走到这里了，就可以找到最大值和最小值然后做差，差值小于等于5就可以了
        TreeSet<Integer> set=new TreeSet<>();
        // 用 TreeSet 来接收 TreeSet new出来的对象，可以多一些子类的方法
        // 因为 Set是父类，父类的方法总是会少一点，子类的方法相对会多了不少
        //善于用子类来创建和接收会更加的方便

        int j=0;//用来计算0的个数

        for(int i=0;i<len;i++){
            if(places[i]==0){
                //此时遍历到的数组元素是0
                j++;
            }else if(!set.contains(places[i])){
                //此时遍历到的数组元素在set中不存在，加入到set中
                set.add(places[i]);
            }else{
//此时遍历到的数组元素在set中存在，不能加入到set中，并且要把bool置为false，因为有重复的年份了
                bool=false;
            }


        }



        int small=set.first();//set中的最小值
        int big=set.last();//set中的最大值




        // 这个数组只有5个元素，所以最大值和最小值的差值如果大于等于5，那么就一定不是连续的了，那么就把bool置为false
        if((big-small)>=5){
            bool=false;
        }

        // 返回结果 bool 的值
        return bool;
    }
}








// 53. 最大子数组和

 class Solution18 {

    //这里使用的是分治法
    public int maxSubArray(int[] nums) {
        return func(nums,0,nums.length-1);
    }

    public static int func(int[] arr,int left,int right){
        if(arr.length==1){
            return arr[0];
        }

        if(left==right){
            return arr[left];
        }

        int mid=(left+right)/2;
        int mleft=func(arr,left,mid);//左子数组的最大字段和
        int mright=func(arr,mid+1,right);//右子数组的最大字段和

        int d=-2147483648;//用来存放最终的最大字段和（最大字段和的最小值为0）
        //先把d的值设为int类型中的最小值，然后继续

        if(mleft<mright){
            d=mright;
        }else{
            d=mleft;
        }

        int i=mid;//往left的方向走
        int j=mid+1;//往right的方向走

        //从中间往2边走，遍历整个数组 找到横跨2个子数组的 最大字段和
        //从中间往2边走，找到从中间坐标开始左边的最大字段和，然后找到从中间坐标开始右边的最大字段和，让2者相加就是横跨左右子数组的最大字段和

        int sleft=-2147483648;
        //先把sleft的值设为int类型中的最小值，然后继续

        int midleft=0;
        while(i>=left){
            midleft+=arr[i];
            i--;
            if(midleft>sleft){
                //找到比sleft大的就更新sleft的值
                sleft=midleft;
            }
        }

        int sright=-2147483648;
        //先把sright的值设为int类型中的最小值，然后继续

        int midright=0;
        while(j<=right){
            midright+=arr[j];
            j++;
            if(midright>sright){
                //找到比sright大的就更新sright的值
                sright=midright;
            }
        }

        int dmid=sleft+sright;
        if(dmid>d){
            d=dmid;
        }


        return d;
    }
}










// 53. 最大子数组和

class Solution17 {

    //这里使用的是动态规划的方式
    //动态规划的这个做法的原理是什么呢？？？？？？
    //去找到 nums数组每个下标位置和它的前一个元素的最大字段和相加，
    //求出每个下标位置包含它的最大字段和是多少

    public int maxSubArray(int[] nums) {
        int[] ret=new int[nums.length];
        ret[0]=nums[0];
        for(int i=1;i<nums.length;i++){
            ret[i]=ret[i-1]+nums[i];
            if(ret[i]<nums[i]){
                ret[i]=nums[i];
            }
        }

        int m=ret[0];
        for(int i=1;i<nums.length;i++){
            if(ret[i]>m){
                m=ret[i];
            }
        }

        return m;

    }
}









// 75. 颜色分类

class Solution16 {
    public void sortColors(int[] nums){

        //计数排序

        int a=0; //记录0的个数
        int b=0; //记录1的个数
        int c=0; //记录2的个数

        int len=nums.length;
        for(int i=0;i<len;i++){
            if(nums[i]==0){
                a++;
            }else if(nums[i]==1){
                b++;
            }else if(nums[i]==2){
                c++;
            }
        }

        //修改数组中对应位置的值
        for(int i=0;i<a;i++){
            nums[i]=0;
        }
        for(int i=a;i<b+a;i++){
            nums[i]=1;
        }
        for(int i=a+b;i<c+b+a;i++){
            nums[i]=2;
        }
    }
}







// 215. 数组中的第K个最大元素

class Solution15 {
    int m=0; //全局变量，用来寻找记录第k大的数是谁
    //第5   index=4   obj = nums.length - k
    public int findKthLargest(int[] nums, int k) {
        // 0--u-1  u  u+1---n-1

        //0--9   10  10--16

        //10--16

        //快排思想，单趟快排思想

        // 快排，选择一个基准，然后让一个i从数组第开头开始走，一个j从数组的尾巴开始走
        // 让尾巴处的j先走，去找比基准值小的元素
        // 然后让开头的i开始走，去找比基准值大第元素，当j和i都找到了他们要找的元素以后，就交换他们第元素位置，
        // 知道他们相遇为止，他们相遇以后，让这个相遇位置和基准值第位置交换（可以让这个基准值就是数组的首元素）

        // 采用类似二分的方式，每次排序后，看一下我们所要找的目标位置在哪一半 ，然后持续进行二分快排


        m=nums[0]; //先把这个全局变量赋值一下，防止出现不在数组里面的值的情况

        //我们要找的是第k大的数，所以说，就是数组排序以后下标为 nums.length-k 位置的值
        //调用func方法，先来得到一个基准值的最终位置
        int ret=func(nums,0,nums.length-1);

        // 记录我们所排序的是数组的哪一部分，所以这里记录了这一部分的 左右坐标，都是闭区间的
        int left=0;
        int right=nums.length-1;

        // 调用funcfind方法，来递归找到目标值 并返回
        int num=funcfind(nums,nums.length-k,ret,left,right);
        return num;
    }

    //返回最终的目标值（数组中的第 k 个最大的元素的值）
    public int funcfind(int[] nums,int k,int ret,int left,int right){
        //通过比较基准值第最终位置ret和目标值的坐标，来找出接下来的快排是针对 哪半部分 来进行的
        if(ret<k){
            //目标值在 右半部分，递归右半部分
            left=ret+1;
            ret=func(nums,left,right);
            m=funcfind(nums,k,ret,left,right);
        }else if(ret>k){
            //目标值在 左半部分，递归左半部分
            right=ret-1;
            ret=func(nums,left,right);
            m=funcfind(nums,k,ret,left,right);
        }else if (ret==k){
            //找到目标值的位置了
            m = nums[ret];
            return m;
        }
        return m;
    }

    // 使用func方法来实现单趟快排
    //返回 基准值 的最终位置坐标
    // [left,right]
    public int func(int[] nums,int left,int right){
        //就使用数组的第一个数来作为基准值吧
        //让i从左往右走，找大
        //让j从右往左走，找小

        // 调用三数取中，找到一个合适的基准值，然后把这个基准值和数组第left下标进行交换
        int mid=midfind(nums,left,right);
        int n=nums[mid];
        nums[mid]=nums[left];
        nums[left]=n;

        // 交换以后，数组的left下标的值就是合适的基准值了
        int ret=nums[left]; //ret是这趟快排第基准值
        int m=left; //记录一下此次 基准值所对应第下标

        //此次排序数组的范围 [left,right] 都是闭区间的
        int i=left;
        int j=right;

        while(i<j){

            //找小
            while(j>=0 && i<j){
                if(nums[j]<ret){
                    break;
                }
                j--;
            }

            //找大
            while(i<j && i<nums.length){
                if(nums[i]>ret){
                    break;
                }
                i++;
            }

            //找到大于基准值的值和小于基准值的值 然后交换
            int tmp=nums[i];
            nums[i]=nums[j];
            nums[j]=tmp;

        }
        //走到这里代表 i==j，可以进行交换操作了
        nums[m]=nums[i];
        nums[i]=ret;
        return i;
    }

    //三数取中 返回三个值中 值的大小在中间的 下标
    public int midfind(int[] nums,int left,int right){
        int a=nums[left];
        int b=nums[right];
        int c=nums[(left+right)/2];
        if(a>b){
            if(c>a){
                return left;
            }
            if(b>c){
                return right;
            }
        }
        if(a<b){
            if(c>b){
                return right;
            }
            if(a>c){
                return left;
            }
        }
        return (left+right)/2;
    }
}










//216. 组合总和 III

class Solution14 {
    //回溯思想
    //和 组合的那个题很像，就是加了一个 个数的限制的感觉。
    // [1,9] 每个数字只能用一次，  返回的  每个组合结果不能重复

    boolean[] check=new boolean[9]; // 用来剪枝，false代表还没有用到；true代表用过了就不能再用了
    List<List<Integer>> array=new ArrayList<>(); //用来存放最终结果
    List<Integer> arr=new ArrayList<>(); // 用来存放中间路径的结果
    int num=0; // 用来存放一条路径中值的和
    int m=0; // 用来存放一条路径中值的个数

    public List<List<Integer>> combinationSum3(int k, int n) {
        int[] nums={1,2,3,4,5,6,7,8,9}; // 先创建[1,9]的一个数组
        func(nums,n,k); //调用子函数func
        return array;
    }

    public void func(int[] nums,int n,int k){
        //当这条路径的和与n相等，并且这条路径的元素个数与k相等的时候，就说明这条路径是我们要的结果之一，就新增到array中
        if(num==n && m==k){
            array.add(new ArrayList<>(arr));
            return;
        }

        // 题目要求一条路径上的元素不重复，所以每次都要往这一元素的后面第位置去找
        // i就是来记录这条路径上已经有了的最大的元素是谁，以此来找到他的下标（因为这个数组是有序的，并且是 [1,9] 的）
        int i=0;
        if(arr.size()>0){
            i=arr.get(arr.size()-1);
        }

        for(;i<nums.length;i++){

            if(check[i]==false){
                // false表示没用过，所以可以添加到arr中，
                // 添加的同时还要把该位置置为true，并且让num加上这个元素，让m++
                arr.add(nums[i]);
                check[i]=true;
                num+=nums[i];
                m++;
                //调用func，继续回溯
                func(nums,n,k);

                //恢复现场,上面修改的都在改回来
                arr.remove(arr.size()-1);
                check[i]=false;
                num-=nums[i];
                m--;
            }
        }
    }
}





//1137. 第 N 个泰波那契数

class Solution13{
    //动态规划，创建数组存储的方式
    public int tribonacci(int n){
        //如果n的值是0，就返回0
        if(n==0){
            return 0;
        }else if(n==1 || n==2){
            //如果n的值是1或者2，就返回1
            return 1;
        }

        int[] dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;

        //数组的前三个数已经是已知的了，所以i从下标为3 的地方开始
        for(int i=3;i<=n;i++){
            int ret=dp[i-1]+dp[i-2]+dp[i-3];
            dp[i]=ret;
        }

        return dp[n];
    }
}





// 22. 括号生成

class Solution12 {
    Set<String> set=new HashSet<>(); //用来对字符串去重
    List<String> array=new ArrayList<>(); //用来存放最终的结果
    StringBuffer str=new StringBuffer(); //用来存放中间结果，String类型不可修改，所以这里使用了StringBuffer这种类型
    int num=0; //用来标记中间结果中已经有几对括号

    public List<String> generateParenthesis(int n) {
        //n n-1的所有结果，得，每一个位置都插入有一个()得来

        //1
        //["()"]

        //2
        //["(())","()()"]

        //3
        //["((()))","(()())","(())()","()(())","()()()"]

        //所以说这个题的思路，也是一个递归的思路，
        // 按照上面的 n=1 n-2 n=3  的例子来看，n=3的情况就是把所有n=2的情况中所得到的结果，把这个结果字符串的所有可以插空的地方都放上一个（），虽然说可能会有重复结果的情况，这个时候我们可以使用set的去重功能来进行求解的操作。
        //n的结果就是n-1的结果中每一位可以插空的地方放上一个（）的情况，使用set来去重
        //所谓的插空的意思就是：假如有一个结果是 ：()
        //那么插空以后可能产生的结果是：()()  (()) ()() 共有三个位置可以插空，
        //去重以后，就只剩下2个了， ()() 和 (())

        //调用子函数来实现功能
        func(n);

        //把set中的值放到array中
        for(String ret : set){
            array.add(ret);
        }

        return array;
    }

    public void func(int n){
        // 当字符串中的括号对数已经满足n对的时候，就可以新增到set中的
        if(num==n){
            //set中的类型是String，所以需要把StringBuffer装换成String类型，然后存到set中
            String string=new String(str);
            set.add(string);
            return;
        }


        int len=str.length();
        //在str字符串中的每一个可以插空的地方都插入一对括号进行尝试
        //所谓的插空的意思就是：假如有一个结果str是 ：   ()
        //那么插空以后可能产生的结果是： ()()  (()) ()()  共有三个位置可以插空，
        //去重以后，就只剩下2个了，  ()() 和 (())
        for(int i=0;i<len+1;i++){
            str.insert(i,"()");
            num++;

            //多了一对括号之后，就递归func方法，直到这一路径满足递归的终止条件
            func(n);

            //加入了什么就要删除掉什么，然后继续for循环，插空字符串的下一个位置
            str.delete(i,i+2);//删除字符串str中第i到第i+1个位置的字符
            num--;
        }

    }
}





// 39. 组合总和

class Solution11 {
    //和组合的那个题可能也有点类似，使用回溯算法试一下

    Set<List<Integer>> set=new HashSet<>(); //用来去重
    List<List<Integer>> array=new ArrayList<>(); //用来存放最终的结果数组
    List<Integer> arr=new ArrayList<>(); //用来存放中间的结果数组
    int num=0; //用来计算现在的累积值

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        Arrays.sort(candidates);
        //对源数组进行排序，如果源数组的第一个数都大于target，就返回
        if(candidates[0]>target){
            return array;
        }

        //调用子函数求解
        func(candidates,target);

        // 把set中已经去重过的数据放到array这个最终结果中
        for(List<Integer> list : set){
            array.add(list);
        }

        return array;

    }

    public void func(int[] candidates,int target){
        if(num==target){
            //System.out.println(1);
            // arr后面还要用不能对它进行排序，要拷贝一份，然后对拷贝的内容进行排序
            ArrayList<Integer> copy = new ArrayList<>(arr);
            Collections.sort(copy);  //对ArrayList类型进行排序
            //放到set中进行去重
            set.add(copy);
            return;
        }else if(num>target){
            return;
        }

        for(int i=0;i<candidates.length;i++){
            arr.add(candidates[i]);
            num+=candidates[i];
            //每找到一个数，就调用func方法,继续往下寻找
            func(candidates,target);

            //回溯，恢复现场（加上了什么就减去什么）
            num-=arr.get(arr.size()-1);
            arr.remove(arr.size()-1);
        }
    }
}




// 77. 组合

class Solution10 {
    //使用回溯算法来进行求解
    //数组内的数是：[1, n] ，一共有n个元素，所以说数组内的每一个元素都是不相等的,并且是有序的

    List<List<Integer>> array=new ArrayList<>(); //用来存放最终结果的数组
    List<Integer> arr=new ArrayList<>(); //用来存放中间结果的数组，存放一条路径上的数据
    boolean[] check=new boolean[20]; //用来剪枝的，false代表还没有用到；true代表用过了就不能再用了

    public List<List<Integer>> combine(int n, int k) {
        //先创建一个[1,n]的数组
        int[] ret=new int[n];
        for(int i=0;i<n;i++){
            ret[i]=i+1;
        }
        //调用子函数，然后直接返回
        func(ret,k);
        return array;
    }

    //子函数func用来实现回溯递归的功能
    public void func(int[] ret,int k){
        //当k的值和arr数组的长度值相等的时候，就是递归的结束条件了
        if(arr.size()==k){
            array.add(new ArrayList<>(arr));
            return;
        }

        //回溯操作
        //题目中的数组[1,n]是从1到n的所以就是天然有序的
        //题目的要求是：从前到后的来找，如果有[1,2]和[2,1]的这种情况，就留着前面的[1,2]就行了
        //所以就是从数组的某个位置来和它后面的位置的元素来进行配对的
        //i就是来做这个的
        int i=0;
        if(arr.size() > 0)
            i = arr.get(arr.size() - 1);

        for(;i<ret.length;i++){
            if(check[i]==false){
                arr.add(ret[i]);
                check[i]=true;
                func(ret,k);

                //回溯：恢复现场
                arr.remove(arr.size()-1);
                check[i]=false;
            }
        }
    }
}




// 47. 全排列 II
class Solution9 {
    //应该也是秉承着 全排列 一题的思路，只不过在加入最终结果的那个二维数组之前，要判断一下结果数组中是否已经有这一组元素的。
    //如果我们使用set来存储就不需要比较是否存在相等的问题了，set自己具有去重的功能

    Set<List<Integer>> set=new HashSet<>(); //set具有去重的功能，可以更方便的进行判断去充电操作
    List<List<Integer>> array=new ArrayList<>(); //存放最终结果的数组
    List<Integer> arr=new ArrayList<>(); // 存放中间结果的数组（存放的是一条路径中的数据组成的数组）
    boolean[] check=new boolean[9]; // 用来剪枝,false代表这个元素在这一条路径中还没有被用到,true则代表被用过了

    public List<List<Integer>> permuteUnique(int[] nums) {
        //调用子函数func来完成回溯递归的功能
        func(nums);

        //然后把set中的元素一一遍历放到array数组中
        //遍历set的方法，可以使用迭代器，也可以使用简单的增强版的for循环
        for(List<Integer> list : set){
            //array.add(list);
            array.add(new ArrayList<>(list));
        }

        //然后返回最终结果的array数组即可
        return array;
    }

    //func函数来实现回溯递归的功能
    public void func(int[] nums){

        //当arr数组的长度和nums数组的长度相等的时候，就是递归的终止条件了，就可以把arr放到set中了
        if(nums.length==arr.size()){
            set.add(new ArrayList<>(arr));
        }

        for(int i=0;i<nums.length;i++){
            //找到一个可以放到arr中的元素，就要调用func方法，继续递归下去
            if(check[i]==false){
                arr.add(nums[i]);
                check[i]=true;

                func(nums);

                //回溯：恢复现场
                if(arr.size()>0){
                    arr.remove(arr.size()-1);
                    check[i]=false;
                }

            }
        }
    }
}



// 46. 全排列
class Solution8 {

    List<List<Integer>> array=new ArrayList<>(); //这个是最终要返回的结果数组
    List<Integer> arr=new ArrayList<>();
    //这个是用来记录每条路径上面的组合的数组，每走完一条路径就把arr的结果添加到array中去
    //判断这一条路径结束的标志是：arr数组的长度和nums数组的长度相等的时候。

    boolean[] check=new boolean[7]; // 负责用来进行剪枝的操作

    public List<List<Integer>> permute(int[] nums) {
        // 数组为： nums = [1,2,3] 下标分别为： 0 1 2
        // 对应的全排列为： [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

        //调用子函数
        func(nums);
        return array;

    }

    public void func(int[] nums){
        //判断若此时的arr数组的长度和nums数组的长度相等，就说明此时 这一条路径已经走完了，也就是走到了叶子节点上了，所以应该把 arr 中的值 添加到 array 中了
        //这也是递归的一个终止条件
        if(arr.size()==nums.length){
            //System.out.println(arr.toString() + " is added in res");

            //把 arr    【中的值】    添加到 array 中了
            array.add(new ArrayList<>(arr));
            return;
        }


        // 接下来开始进行回溯
        int len=nums.length;
        for(int i=0;i<len;i++){
            //找到arr数组中的一个元素的话 就继续调用func函数，直到满足终止条件为止
            if(check[i]==false){
                arr.add(nums[i]);
                check[i]=true;
                func(nums);

                //回溯：恢复一下现场
                arr.remove(arr.size()-1);
                check[i]=false;
            }

        }
    }
}



 // 78. 子集
class Solution7 {
    //找到一个数组的所有子集，假如数组是：nums = [1,2,3]
    //那么它的子集有：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 这8个
    //空集是任何集合的子集，所以无论是怎样的数组，都会有空集这个子集的
    //其他的7个子集：分别对应原数组中的下标
    // [] [0] [1] [2] [0,1] [0,2] [2,3] [1,2,3]
    //再解读一下这些对应的下标：
    // [000] [100] [010] [001] [110] [101] [011] [111]
    // 也就是说就是二进制的从 [000] 到 [111] 的序列
    //（之所以是到111也是因为上面的nums数组的长度是3，所以就是3个1 ）

    public List<List<Integer>> subsets(int[] nums) {
        //先创建一个二维数组，然后每找到一个目标子集就放到这个数组中去
        //按照上面分析的规则来看，如果数组的长度是3 ，那么它的子集个数就是：8个
        //所以说：如果数组的长度是n,那么它的子集个数就有2^n个

        int len=nums.length;
        List<List<Integer>> array=new ArrayList<>();

        //约定对于nums数组，每一位的值如果用到了就是1，没用到就是0

        int num=1; //在此处我们先使用num来求出数组长度个1的二进制所对应的十进制数字
        for(int i=0;i<len;i++){
            num*=2;
        }

        //然后使用ret来计量子集的个数，达到目标值num以后就说明都找到了
        // ret的另一个作用就是通过它的二进制来找到每一个子集的对应元素
        int ret=0;
        while(ret<num){
            //接下来这里把ret转换成要给二进制的数字，然后对nums数组进行遍历，找到目标子集数组
            int[] mn=func(ret,len);
            //调用了把ret转换成二进制的函数

            List<Integer> arr=new ArrayList<>();

            for(int j=0;j<len;j++){
                if(mn[j]==1){

                    //值为1代表在子集里面，所以add
                    arr.add(nums[j]);
                }
            }
            ret++;

            //之后要把这个找到的子集新增放到目标的二维数组中
            array.add(arr);
        }

        return array;
    }

    public int[] func(int ret,int len){
        //把一个整数转换成二进制

        int[] arr=new int[len];
        int i=len-1; //从后开始存储每次得到的 0/1
        while(ret!=0){
            arr[i]=ret%2;
            ret=ret/2;
            i--;
        }
        return arr;
    }
}




// 2255. 统计是给定字符串前缀的字符串数目（注意理解题意）
class Solution6 {
    public int countPrefixes(String[] words, String s) {
        //字符串的检索的方法是 indexOf ：
        // int indexOf(String str)
        //从指定位置(0或fromIndex)开始，返回第一次出现str的位置。若未找到返回-1。

        int count=0;
        for(int i=0;i<words.length;i++){
            //words[i]位置的字符串 如果长度小于s,则s包含words[i]字符串
            int b=s.indexOf(words[i]);
            //只要words[i]包含s字符串 或者 s包含words[i]字符串其中有一个成立，
            //并且indexOf方法的返回值是0，就符合条件,count就++
            if(b==0){
                count++;
            }
        }

        //请你返回 words 中是字符串 s 前缀 的 字符串数目 。
        //所以说这个题的意思是：要找出words数组中，长度小于等于s的，并且是 s前缀 的元素数量
        //就是要找出在words数组中，有几个元素是s字符串的子串，并且是s字符串的前缀

        return count;
    }
}



// 1184. 公交站间的距离
class Solution5 {
    public int distanceBetweenBusStops(int[] distance, int start, int destination){
        //正着计算一下，反着计算一下路径 然后比大小
        int a1=0;
        int a2=0;
        if(start>destination){
            int ret=start;
            start=destination;
            destination=ret;
        }
        //start的值一定是小于destination的了
        int tmp=destination-start;
        //正着
        for(int i=0;i<tmp;i++){
            a1+=distance[start];
            start++;
        }
        int size=distance.length;
        //反着
        for(int i=0;i<size;i++){
            a2+=distance[i];
        }
        //用数组的总长度减去正着路径的长度就是反着路径的长度了
        int a3=a2-a1;
        //返回较小的值
        if(a3>a1){
            return a1;
        }
        return a3;
    }
}


// 796.旋转字符串
class Solution4 {
    public boolean rotateString(String s, String goal) {
        int s1=s.length();
        int s2=goal.length();
        //如果这2个字符串的大小不一样，那就一定不是旋转得到的关系
        if(s1!=s2){
            return false;
        }
        //把s这个字符串的2份拼接成一份，然后 所有旋转s这个字符串所产生的字符串  都会存在于这个 新字符串 中。
        String str=s+s;
        // contains 方法，是用来判断字符串中是否包含某一个字串
        return str.contains(goal);
    }
}



//翻转单词顺序
class Solution3 {
    public String reverseWords(String s) {
        //把字符串变成字符串数组，然后逆置数组元素
        //空格不作为字符串数组的有效元素值
        String[] str=s.split(" ");

        int len=str.length;
        // 遍历翻转数组
        int i=0;
        int j=len-1;
        while(i<j){
            if(str[i]!="" && str[j]!=""){
                String ret=str[i];
                str[i]=str[j];
                str[j]=ret;
                i++;
                j--;
            }
            if (str[i]==""){
                i++;
            }
            if (str[j]==""){
                j--;
            }
        }


        String zy="";
        for(int e=0;e<len;e++){
            if(str[e]!=""){
                zy+=str[e];
                if(e!=len-1){
                    zy+=" ";
                }
            }
        }
        return zy;
    }
}




//520. 检测大写字母
class Solution {
    //判断字符串除了首字符以外的位置是否都是大写的
    public boolean isbig(String str){
        int size=str.length();
        boolean bool=true;
        for(int i=1;i<size;i++){
            char ch=str.charAt(i);
            if(ch>='a'&&ch<='z'){
                bool=false;
                break;
            }
        }
        return bool;
    }

    //判断字符串除了首字符以外的位置是否都是小写的
    public boolean issmall(String str){
        int size=str.length();
        boolean bool=true;
        for(int i=1;i<size;i++){
            char ch=str.charAt(i);
            if(ch>='A'&&ch<='Z'){
                bool=false;
                break;
            }
        }
        return bool;
    }
    public boolean detectCapitalUse(String word) {
        boolean bool=false;

        char ch=word.charAt(0);
        //判断首字母是大写的还是小写的
        if(ch>='A'&&ch<='Z'){
            //首字母是大写的
            boolean a1=isbig(word);
            boolean a2=issmall(word);
            if(a1==true||a2==true){
                bool=true;
            }
        }else{
            //首字母是小写的
            boolean b1=issmall(word);
            if(b1==true){
                bool=true;
            }
        }
        return bool;
    }
}






//完美数
class Solution1 {
    public boolean checkPerfectNumber(int num) {
        int tmp=0;
        if(num==1){
            return false;
        }
        for(int i=1;i<=Math.sqrt(num);i++){
            if(num%i==0){
                tmp+=i;
                int ret=num/i;
                if(ret!=num && ret!=i){
                    tmp+=ret;
                }
            }
        }
        if(tmp==num){
            return true;
        }
        return false;
    }
}






public class Test {
    public static void main(String[] args) {
        System.out.println("hello");
    }



    public static void main3(String[] args) {

        System.out.println();
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list=new ArrayList<>();
        List<Integer> ret=new ArrayList<>();
        //要是目标值小于数组中最小的那个数字，那么就直接返回，就说明不存在合适的组合。
        //所以要先找到数组中最小的那个数
        int mini=candidates[0];
        int len =candidates.length;
        for(int i=0;i<len;i++){
            if(mini>candidates[i]){
                mini=candidates[i];
            }
        }
        if(target<mini){
            return list;
        }

        //接下来可以找到所有比目标值小的数字，放到一个新的数组里面
        int[] tmp=new int[len];
        int j=0;
        for(int i=0;i<len;i++){
            if(candidates[i]<=target){
                tmp[j++]=candidates[i];
            }
        }
        //然后对这个临时数组进行排序操作
        Arrays.sort(tmp);
        //现在这个tmp数组就是排好序的数组了，（从小到大）

        return list;
    }


    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        return list;
    }


    public static void main1(String[] args) {
        List<Integer> list=getRow(3);
        System.out.println(list.toString());
    }
    public static List<Integer> getRow(int rowIndex) {
        //行数是从0开始计数的。
        //需要返回的顺序表的首位是1，末位也是1
        List<Integer> list=new ArrayList<>();
        list.add(1);
        //要返回的是第一行
        if(rowIndex==0){
            return list;
        }
        //要返回的比第一行大
        List<Integer> ret=getRow(rowIndex-1);
        for(int i=0;i<ret.size()-1;i++){
            list.add(ret.get(i)+ret.get(i+1));
        }
        list.add(1);
        return list;
    }



}
